import org.junit.jupiter.api.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * @author ZhengDp
 * @Date 2023/4/24 15:54
 */
public class 布隆过滤器_LRUCache {

    @Test
    void test(){
        LRUCache cache = new LRUCache(1);
        cache.put(2,1);
        cache.get(2);

    }

}

/*
 * #problem 146 LRU缓存
 * 最近最少使用
 * */
class LRUCache {

    private class Node {
        int val;
        int key;
        Node next, prev;

        public Node(int key, int val) {
            this.val = val;
            this.key = key;
        }

        public Node() {
        }
    }

    private int capacity;
    private int size;
    private Map<Integer, Node> memo = new HashMap<>();
    private Node head, tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        head = new Node();
        tail = head;
    }

    // get时，需要更新最近最少使用的元素
    public int get(int key) {
        Node node = memo.get(key);
        if(node == null) {
            return -1;
        }
        if(node != tail) {
            removeNode(node);
            tailAddNode(node);
        }
        return node.val;
    }

    // put的时候，如果capacity 已满，需要删除最近最少使用的元素
    public void put(int key, int value) {
        if(memo.containsKey(key)) {
            memo.get(key).val = value;
            get(key);
        } else {
            if (isFull()) {
                Node removeNode = delHeadNode();
                memo.remove(removeNode.key);
            }
            Node node = new Node(key, value);
            tailAddNode(node);
            memo.put(key, node);
        }

    }


    private boolean isFull() {
        return size == capacity;
    }

    private void removeNode(Node node){
        Node pre = node.prev;
        Node next = node.next;
        next.prev = pre;
        pre.next = next;
        size--;
    }

    // 删除头部元素
    private Node delHeadNode() {
        Node removeNode = head.next;
        if(removeNode.next != null) {
            removeNode.next.prev = head;
        }
        head.next = removeNode.next;
        removeNode.next = null;
        removeNode.prev = null;
        size--;
        if (size == 0) {
            tail = head;
        }
        return removeNode;
    }

    // 尾插法
    private void tailAddNode(Node node) {
        node.next = tail.next;
        node.prev = tail;
        tail.next = node;
        tail = node;
        size++;
    }

}
